class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def dfs(self, root: TreeNode, target: int) -> int:
        if root is None:
            return 0

        if root.val != target:
            return 0

        return max(self.dfs(root.left, target), self.dfs(root.right, target)) + 1

    def preOrder(self, root: TreeNode) -> int:
        if root is None:
            return 0

        a = 1 + self.dfs(root.left, root.val) + self.dfs(root.right, root.val)
        b = self.preOrder(root.left)
        c = self.preOrder(root.right)

        return max(a, b, c)

    def longestUnivaluePath(self, root: TreeNode) -> int:
        if root is None:
            return 0

        return self.preOrder(root) - 1
